# A bloody large number.
INFINITY = 1.0e400
from our_adds.agent_smith import AgentSmith
from general import get1Successor
from time import clock

SAFE_EXT = 0.001

class AlphaBetaSearchImproved:
    '''
    This search algorithm implements the limited-resource minimax tree search 
    algorithm with alpha-beta pruning for zero-sum games. This version cuts off 
    search by depth alone and uses an evaluation function (utility).
    '''
    
    def __init__(self, player, max_depth, utility, agent):
        '''
        Constructor.
        
        @param player: Your player. This search algorithm will choose the best
                       actions for this player.
        @param max_depth: The depth of the search tree.
        @param utility: An evaluation function for states.
        @param agent: the agent
        '''
        self.player = player
        self.max_depth = max_depth
        self.utility = utility
        self.agent = agent
    
    def search(self, current_state, time2run):
        '''
        Search game to determine best action; use alpha-beta pruning.
        
        @param current_state: The current game state to start the search from.
        '''
        
        ' set start time '
        initTime = clock()
        safe_time2run = float(time2run) - SAFE_EXT
        best_value = -INFINITY
        ''' I think we should find something better here.........'''
        (action,best_action) = get1Successor(current_state) 
        if (clock() - initTime < safe_time2run):
            ' ~~ changed here : use priority queue '
            res = self.agent.getSuccImproved(current_state)
            successors = res[0]
        else:
            return best_action
        
        while ((len(successors) != 0) and (clock() - initTime < safe_time2run)):
            ' remove one item from the queue '
            (action, state) = successors.pop()
            ' for case there is no time to return nothing'
            #for action, state in current_state.getSuccessors().items():
            value_fn = self._getValueFn(state)
            value = value_fn(state, best_value, INFINITY, 1, initTime, safe_time2run)
            if value > best_value:
                best_value = value
                best_action = action
        return best_action
    
    def _getValueFn(self, state):
        if state.getCurrentPlayer() == self.player:
            return self._maxValue
        else:
            return self._minValue
    
    def _cutoffTest(self, state, depth):
        return depth >= self.max_depth or (state.getWinner() is not None)
    
    def _maxValue(self, state, alpha, beta, depth, initTime, safe_time2run):
        if self._cutoffTest(state, depth):
            return self.utility(state)
        'TODO add time here and in the following code'        
        value = -INFINITY
        if (clock() - initTime < safe_time2run):
            ' ~~ changed here : use priority queue '
            res = self.agent.getSuccImproved(state)
            successors = res[0]
        else:
            return value
        while ((len(successors) != 0) and (clock() - initTime < safe_time2run)):
            ' remove one item from the queue '
            (action, successor) = successors.pop()
            #for successor in successors.values():s
            value_fn = self._getValueFn(successor)
            value = max(value, value_fn(successor, alpha, beta, depth + 1, initTime, safe_time2run))
            if value >= beta:
                return value
            alpha = max(alpha, value)
        
        return value
    
    def _minValue(self, state, alpha, beta, depth, initTime, safe_time2run):
        if self._cutoffTest(state, depth):
            return self.utility(state)
        
        value = INFINITY
        if (clock() - initTime < safe_time2run):
            ' ~~ changed here : use priority queue '
            res = self.agent.getSuccImproved(state)
            successors = res[0]
        else:
            return value
        while ((len(successors) != 0) and (clock() - initTime < safe_time2run)):
            ' remove one item from the queue '
            res = successors.pop()
            action = res[0]
            successor = res[1]
            #for successor in successors.values():
            value_fn = self._getValueFn(successor)
            value = min(value, value_fn(successor, alpha, beta, depth + 1, initTime, safe_time2run))
            if value <= alpha:
                return value
            beta = min(beta, value)
        
        return value

